import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-11-08
 * Time:10:26
 */
class Solution {

    public int removeElement(int[] nums, int val) {
        int sum= nums.length;
        if(sum==0){
            return 0;
        }
        int left=0;
        int right=sum-1;
        while(left<right){
            if(nums[left]==val&&nums[right]!=val){
                nums[left]=nums[right];
                nums[right]=0;
                left++;
                right--;
                sum--;
            }
            if(nums[left]!=val){
                left++;
            }
            if(nums[right]==val){
                nums[right]=0;
                right--;
                sum--;
            }

        }
        if(nums[right]==val){
            nums[right]=0;
            sum--;
        }
        return sum;
    }
    public int removeDuplicates(int[] nums) {
//            if(nums == null || nums.length == 0) return 0;
//            int p = 0;
//            int q = 1;
//            while(q < nums.length){
//                if(nums[p] != nums[q]){
//                    nums[p + 1] = nums[q];
//                    p++;
//                }
//                q++;
//            }
//            return p + 1;

        if(nums.length<2){
            return nums.length;
        }
        int sum=0;
        int cur=1;
        //一直找到相等的
//        while(nums[cur]!=nums[sum]){
//            cur++;
//            sum++;
//            if(cur>= nums.length){
//                break;
//            }
//        }
        while(cur<nums.length){
            if(nums[cur]==nums[sum]){
                cur++;
            }else{
                nums[sum+1]=nums[cur];
                sum++;
            }
        }
        return sum+1;
    }
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=0;
        int j=0;
        //从小往大找
        while(i<m&&j<n){
            //小于，
            if(nums1[i]<=nums2[j]){
                i++;
            }else{
                //大于的时候，所有的向后挪，加入nums2
                for (int k =nums1.length-1; k >i; k--) {
                    nums1[k]=nums1[k-1];
                }
                nums1[i]=nums2[j];
                j++;
                i++;
                m++;
            }
        }
        while(j<n){
            nums1[i]=nums2[j];
            i++;
            j++;
        }
    }
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
            int i=m-1;
            int j=n-1;
            int k=m+n-1;
            while(j>=0){
                //需要交换
                //不需要交换
                if(i>=0){
                    if(nums1[i]>=nums2[j]){
                        nums1[k--]=nums1[i--];
                    }else{
                        nums1[k--]=nums2[j--];
                    }
                }else {
                    //nums2没有结束
                    nums1[k--]=nums2[j--];
                }
            }
    }
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list=new LinkedList<>();
        List<Integer> list1=new LinkedList<>();
        list1.add(1);
        list.add(list1);
        if(numRows<1){
            return list;
        }
        for (int i = 1; i < numRows; i++) {
            List<Integer> cur=new LinkedList<>();
            cur.add(1);
            for (int j = 1; j < i; j++) {
                cur.add(list.get(i-1).get(j)+list.get(i-1).get(j-1));
            }
            cur.add(1);
            list.add(cur);
        }
        return list;
    }
}

public class Test {
    public static void main(String[] args) {
        MyArrayList myArrayList=new MyArrayList();
        myArrayList.add(1);
        myArrayList.add(2);
        myArrayList.add(3);
        myArrayList.add(4);
        myArrayList.add(5);
        myArrayList.add(6);
        myArrayList.add(7);
        myArrayList.add(8);
        myArrayList.add(9);
        myArrayList.add(0);
        myArrayList.add(3,2);
        myArrayList.display();
    }
    public static void main1(String[] args) {
        int []array={1,1,2};
        Solution s=new Solution();
        //s.removeElement(array,0);
        //System.out.println(Arrays.toString(array));
//        int a=s.removeDuplicates(array);
//        System.out.println(a);
//        System.out.println(Arrays.toString(array));
        //int []nums1={1,2,3,0,0,0};
        //int[]nums2={3,4,5};
//        int []nums1={1,2,3,0,0,0};
//        int[]nums2={2,5,6};

        //s.merge(nums1,3,nums2,3);
//        List<List<Integer>> list=s.generate(6);
//        System.out.println();
    }
}
